package sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/6/24-19:49
 * 插入排序
 * 插入排序（Insertion Sorting）的基本思想是：
 * 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，
 * 无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，
 * 把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
 */
public class InsertSort {
    public static void insert(int[] arr) {
        int insertIndex;
        int insertValue;
        for (int i = 1; i < arr.length; i++) {
            insertIndex = i;//记录索引要插入值的索引用于判断是否改变
            insertValue = arr[i];//要插入的元素
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > insertValue) {//与前面的参数比较
                    arr[j + 1] = arr[j];//元素后移一位
                    insertIndex = j;//记录要插入的位置
                }else{
                    break;
                }
            }
            if (insertIndex != i) {//如果索引插入索引发生变化
                arr[insertIndex] = insertValue;//插入元素
            }
        }

    }


    public static void insert2(int[] arr) {
        int insertIndex;
        int insertValue;
        for (int i = 0; i < arr.length; i++) {
            insertIndex = i;//记录索引要插入值的索引用于判断是否改变
            insertValue = arr[i];//要插入的元素9+

            for (int j = i-1; j >=0 ; j--) {
                //与前面的参数比较
                if (arr[j]>insertValue){
                    //元素后移一位
                    arr[j+1] =arr[j];
                    //记录要插入的位置
                    insertIndex=j;
                }
            }
            if (insertValue!=arr[insertIndex]){
                arr[insertIndex]=insertValue;
            }

            //如果索引插入索引发生变化
            //插入元素
        }

    }

    public static void insert3(int[] arr) {
        int insertIndex;
        int insertValue;
        for (int i = 0; i < arr.length; i++) {
            insertIndex = i;//记录索引要插入值的索引用于判断是否改变
            insertValue = arr[i];//要插入的元素9+
            for (int j = i-1; j >=0 ; j--) {
                if (arr[j]>insertValue){
                    arr[j+1] = arr[j];
                    insertIndex = j;
                }
            }
            if (insertValue!=arr[insertIndex]){
                arr[insertIndex] = insertValue;
            }

        }
    }
}
